package org.example.everyday;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

/**
 * https://leetcode-cn.com/problems/map-of-highest-peak/
 */
public class HighestPeak {
    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public static void main(String[] args) {
        int[][]isWater = new int[][]{{0,1},{0,0}};
        HighestPeak h = new HighestPeak();
        isWater = h.highestPeak(isWater);

        for (int i = 0; i < isWater.length; i++) {
            for (int j = 0; j < isWater[i].length; j++) {
                System.out.print( isWater[i][j]);
            }
        }

    }

    public int[][] highestPeak(int[][] isWater) {
        if(isWater == null || isWater.length == 0){
            return new int[][]{};
        }
        int m = isWater.length,n = isWater[0].length;
        Queue<int[]> queue = new ArrayDeque<>();
        int[][] ans = new int[m][n];
        for (int i = 0; i < ans.length; i++) {
            Arrays.fill(ans[i],-1);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                //如果是水域
                if(isWater[i][j] == 1){
                    queue.offer(new int[]{i,j});
                    ans[i][j] = 0;
                }
            }
        }

        //BFS过程
        while (!queue.isEmpty()){
            int[] p = queue.poll();
            for (int[] dir:dirs){
                int dx = p[0]+dir[0],dy = p[1]+dir[1];
                if(dx>=0 && dx<m && dy>=0 && dy<n && ans[dx][dy] == -1){
                    ans[dx][dy]  = ans[p[0]][p[1]]+1;
                    queue.offer(new int[]{dx,dy});
                }
            }
        }
        return ans;
    }
}
